1. Field of the Invention
The present invention relates to variable-length coding for data compression, and in particular the variable-length coding of (run, level) pairs.
2. Background Art
Variable-length coding (VLC) is a well-known technique of data compression. If certain data patterns occur much more often than other data patterns, then data compression occurs if the frequent data patterns are assigned shorter variable-length codes, and the infrequent data patterns are assigned longer variable-length codes. The technique has been well known since the introduction of the Morse code for telegraphy in the 19th century. The Morse code, for example, is a set of variable-length code words, each of which is comprised of a series of “dots” and “dashes.” The most frequently used letters of the alphabet (E and T) are assigned the shortest code words, consisting of a single dot for the letter E, and a single dash for the letter T.
For encoding pictures or audio-visual data, the variable-length coding often encodes (run, level) pairs. Typically the run represents the number of consecutive zero-valued transform coefficients in a series of transform coefficients, and the level represents the nonzero value of a transform coefficient which terminates the above chain of zero valued coefficients. For example, a number of standard image compression techniques subdivide a picture into 8×8 blocks of pixels. For each block, a two-dimensional discrete cosine transform is applied to the pixel values to produce a series of 64 DCT coefficients. The coefficient values are quantized in such a way that a large number of the coefficients typically have a level of zero, and most of the coefficients have relatively small level magnitudes.
There are various ways that (run, level) pairs can be variable-length coded. In a common coding scheme, each of the most frequent (run, level) pairs is assigned a corresponding variable-length code having a length that is inversely proportional to the frequency of the (run, level) pair. The less frequent (run, level) pairs, however, are encoded in a different fashion, which will be referred to as an escape sequence. For example, the escape sequence is a fixed-length code word, consisting of an escape code, followed by the run value and the level value. Such variable-length coding of (run, level) pairs is used in a popular video compression technique known as MPEG.
MPEG is an acronym for the Moving Picture Experts Group, which was set up by the International Standards Organization (ISO) to work on compression of video and its associated audio. MPEG provides a number of different variations (MPEG-1, MPEG-2, etc.) to suit different bandwidth and quality constraints. MPEG-2, for example, is especially suited to the storage and transmission of broadcast quality television programs.
For the video data, MPEG provides a high degree of compression (up to 200:1) by encoding 8×8 blocks of pixels into a set of discrete cosine transform (DCT) coefficients, quantizing and encoding the coefficients, and using motion compensation techniques to encode most video frames as predictions from or between other frames. In particular, the encoded MPEG video stream is comprised of a series of groups of pictures (GOPs), and each GOP begins with an independently encoded (intra) I frame and may include one or more following P frames and B frames. Each I frame can be decoded without information from any preceding and/or following frame. Decoding of a P frame in general requires information from a preceding frame in the same GOP. Decoding of a B frame in general requires information from both a preceding frame which can be in the previous or the same GOP, and a following frame in the same GOP. To minimize decoder buffer requirements, transmission orders differ from presentation orders for some frames, so that all the information of the reference frames required for decoding a non-causally predicted frame, that is to say a B frame will arrive at the decoder before the B frame.
In addition to the motion compensation techniques for video compression, the MPEG standard provides a generic framework for combining one or more elementary streams of digital video and audio, as well as system data, into single or multiple program transport streams (TS) which are suitable for storage or transmission. The system data includes information about synchronization, random access, management of buffers to prevent overflow and underflow, and time stamps for video frames and audio packetized elementary stream packets embedded in video and audio elementary streams as well as program description, conditional access and network related information carried in other independent elementary streams. The standard specifies the organization of the elementary streams and the transport streams, and imposes constraints to enable synchronized decoding from the audio and video decoding buffers under various conditions.
The MPEG-2 standard is documented in ISO/IEC International Standard (IS) 13818-1, “Information Technology-Generic Coding of Moving Pictures and Associated Audio Information: Systems,” ISO/IEC IS 13818-2, “Information Technology-Generic Coding of Moving Pictures and Associated Audio Information: Video,” and ISO/IEC IS 13818-3, “Information Technology-Generic Coding of Moving Pictures and Associated Audio Information: Audio,” which are incorporated herein by reference. A concise introduction to MPEG is given in “A guide to MPEG Fundamentals and Protocol Analysis (Including DVB and ATSC),” Tektronix Inc., 1997, incorporated herein by reference.